Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Tree
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Level Order Traversal Pattern (easy)
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Even Odd Tree

Problem Statement

Given a binary tree, return true if it is an Even-Odd tree. Otherwise, return false.

The Even-odd tree must follow below two rules:

  1. At every even-indexed level (starting from 0), all node values must be odd and arranged in strictly increasing order from left to right.
  2. At every odd-indexed level, all node values must be even and arranged in strictly decreasing order from left to right.

Examples

Example 1

  • Input:
    1
   / \
  10  4
 / \
3   7
  • Expected Output: true
  • Justification: The tree follows both conditions for each odd and even level. So, it is an odd-even tree.

Example 2

Input:

    5
   / \
  9   3
 /     \
12      8
  • Expected Output: false
  • Justification: Level 1 has Odd values 9 and 3 in decreasing order, but it should have even values. So, the tree is not an odd-even tree.

Example 3

  • Input:
    7
   / \
  10  2
 / \
12  8
  • Expected Output: false
  • Justification: At level 2 (even-indexed), the values are 12 and 8, which are even, but they should have odd values. So, the tree is not an odd-even tree.

Constraints:

  • The number of nodes in the tree is in the range [1, 105].
  • 1 <= Node.val <= 106

Solution

To solve this problem, we can perform a level-order traversal (BFS) of the binary tree. During this traversal, we will keep track of the current level index to check whether it is even or odd. For each level, we will store the node values and verify the required conditions:

  • If the level is even, the values should be odd and in strictly increasing order.
  • If the level is odd, the values should be even and in strictly decreasing order.

This approach is efficient because it allows us to traverse each node once and check the conditions in a single pass. By maintaining a queue for BFS and lists for each level's values, we can ensure that all conditions are checked accurately.

Step-by-step Algorithm

  1. Initialize a queue for level-order traversal and add the root node to it.
  2. Initialize a variable level to 0 to keep track of the current level.
  3. While the queue is not empty:
    • Determine the number of nodes at the current level (size).
    • Create an empty list (values) to store the values of the nodes at the current level.
    • For each node in the current level:
      • Remove the node from the queue.
      • Add its value to the values list.
      • If the node has a left child, add it to the queue.
      • If the node has a right child, add it to the queue.
    • Check the values collected at the current level:
      • If the level is even:
        • Ensure all values are odd and strictly increasing.
      • If the level is odd:
        • Ensure all values are even and strictly decreasing.
    • If the values do not meet the required conditions, return false.
    • Increment the level by 1.
  4. Return true if all levels meet the required conditions.

Algorithm Walkthrough

Input Tree:

    1
   / \
  10  4
 / \
3   7

Steps:

  1. Initialization:

    • Queue: [1]
    • Level: 0
  2. Level 0:

    • Size: 1
    • Values: []
    • Process node 1:
      • Queue: []
      • Values: [1]
      • Add left child (10) to the queue
      • Add right child (4) to the queue
    • Check values for even level:
      • Values: [1] (all odd and strictly increasing)
    • Increment level: 1
  3. Level 1:

    • Size: 2
    • Values: []
    • Process node 10:
      • Queue: [4]
      • Values: [10]
      • Add left child (3) to the queue
      • Add right child (7) to the queue
    • Process node 4:
      • Queue: [3, 7]
      • Values: [10, 4]
    • Check values for odd level:
      • Values: [10, 4] (all even and strictly decreasing)
    • Increment level: 2
  4. Level 2:

    • Size: 2
    • Values: []
    • Process node 3:
      • Queue: [7]
      • Values: [3]
    • Process node 7:
      • Queue: []
      • Values: [3, 7]
    • Check values for even level:
      • Values: [3, 7] (all odd and strictly increasing)
    • Increment level: 3
  5. Completion:

    • Queue is empty, all levels meet the required conditions.
    • Return true.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The algorithm performs a level-order traversal of the binary tree, which means it visits each node exactly once. Therefore, the time complexity is , where n is the number of nodes in the tree.

Space Complexity

The space complexity is determined by the maximum number of nodes at any level in the binary tree. In the worst case, this can be in a perfectly balanced tree. The space required for the queue in the level-order traversal is proportional to the number of nodes at the deepest level, which is in the worst case, simplifying to .

Even Odd Tree (medium)
N-ary Tree Level Order Traversal (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity